/*
 * @lc app=leetcode.cn id=53 lang=cpp
 *
 * [53] 最大子数组和
 */

// @lc code=start
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int dp = nums[0];
        int pre = 0;
        for (int i = 0; i < n; i++) {
            pre = max(nums[i], pre + nums[i]);
            dp = max(dp, pre);
        }
        return dp;
    }
};
// @lc code=end

